The quality of computer graphics display system images and the time required to process these images have been steadily improving with each new generation of graphics display equipment. Continued improvement is clearly beneficial since images which approach photographic quality and project a real-world paradigm are much easier to interpret, while high speed processing allows more productive user interaction with displayed images. For example, currently available graphics display systems are able to provide highly interactive images with shading of displayed objects. Screen shading accurately models the surface effects of different types of lighting sources on displayed objects and the shading effects provide visible cues as to the shape and contours of the objects. Much of the processing required to produce shading effects is done in hardware which interpolates colors between polygon vertices, e.g., using a well known technique such as Gouraud Shading.
Other visual cues such as surface textures, motion blur, object reflections and shadows can also be added an image to further improve its quality. However, these enhancements traditionally require extensive software processing cycles, which make the graphics system less user interactive. The present invention specifically addresses improving the processing time for one of these enhancements, namely, generating shadows cast when objects block the illumination of one or more defined light sources in a scene to be rendered.
Typical computer graphics systems are capable of determining the surface color of an object at a given pixel and whether a pixel is visible from a defined viewpoint, and therefore whether the pixel belongs in the associated frame buffer. To accomplish this it is necessary to perform an interpolation of R, G, B and Z in X, Y space (six-axis interpolation). Since any information as to the positional relationship between light sources and objects is discarded by the geometry processing engine of the graphics system after the lighting calculation step, it is impossible for the subsequent raster processing sub-system to determine if an object casts a shadow on another object to appear in the pixel image.
As described by P. Bergeron in an IEEE September, 1986 publication entitled "A General Version of Crow's Shadow Volumes" (pp. 17-28), there are presently five known classes of shadow generation algorithms. Namely:
(1) Shadow computation during display (A. Appel, "Some Techniques for Shading Machine Renderings of Solids," Proc. Spring Joint Computer Conference, Thompson Books, Washington, DC, pp. 37-45, 1968); PA1 (2) Polygon shadow generation based on clipping transformation (Atherton and Weiler, "Polygon Shadow Generation," Computer Graphics, (Proc SIGGRAPH 78) Vol. 12, No. 3, pp. 275-281, July 1978; PA1 (3) Shadow volumes (F. Crow, "Shadow Algorithms for Computer Graphics," Computer Graphics (Proc. SIGGRAPH 77) Vol. 11, No. 3, pp. 242-248, July 1977; PA1 (4) Z-buffer shadow computation (L. Williams, "Casting Curved Shadows on Curved Surfaces," Computer Graphics, (Proc. SIGGRAPH 78), Vol. 12, No. 3, pp. 270-274, July 1978; and PA1 (5) Ray tracing (see Whitted, "An Improved Illumination Model for Shaded Display," Comm. ACM, Vol. 23, No. 6, pp. 343-349, June 1980).
Of the above techniques, only the Z-buffer algorithm approach described by L. Williams operates in image space and allows a scene of any complexity to be handled. Briefly described, the Williams shadow generation method utilizes two passes through a Z-buffer algorithm, one for a viewer and one for a light source. Determination of whether a surface is to be shadowed is made by using image-precision calculations.
The Williams algorithm begins by calculating and storing just the Z-buffer values for an image from the perspective of the light source, wherein increasing values represent increasing distance. Next, the Z-buffer and the image are calculated from the viewpoint of an observer using a Z-buffer algorithm with the following modification. Whenever a pixel is determined to be visible, its object-precision coordinates in the observer's view (X.sub.O,Y.sub.O,Z.sub.O) are each computationally transformed into coordinates in the light source's view (X'.sub.O,Y'.sub.O,Z'.sub.O) The transformed coordinates X'.sub.O and Y'.sub.O are used to select a value Z.sub.L in the light source's Z-buffer to be compared with the transformed value Z'.sub.O. If Z.sub.L is closer to the light source than is Z'.sub.O, then there is something blocking the light from that point, and the pixel is shaded as being in shadow; otherwise, the point is visible from the light and it is shaded as being lighted. This computationally intensive approach requires extensive transformation calculations between the light source and viewpoint view coordinates for each pixel. Because of these computations, user interactiveness with the computer graphics system is less than optimal, and degrades significantly with the addition of a second or more light source.
Thus, a need continues to exist in the computer graphics processing art for a new shadow generation technique which solves the shadow generation problem in image space and improves upon the performance of previous shadowing approaches.